package com.zhugang.week13.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: findSwapValues
 * @author: chanzhugang
 * @create: 2022/12/09 10:58
 */
public class FindSwapValues {

    /**
     * 面试题 16.21 交换和
     * https://leetcode.cn/problems/sum-swap-lcci/
     *
     * @param array1
     * @param array2
     * @return
     */
    public int[] findSwapValues(int[] array1, int[] array2) {
        /**
         * 两个数组分别求和 sum1、sum2，其中一个数组构建哈希集合， diff = sum/2 - sum1， diff + arr1[i] 在哈希集合中
         */
        int sum1 = 0;
        for (int arr : array1) {
            sum1 += arr;
        }
        int sum2 = 0;
        Set<Integer> set = new HashSet<>();
        for (int arr : array2) {
            sum2 += arr;
            set.add(arr);
        }
        int sum = sum1 + sum2;
        if (sum % 2 == 1) {
            // 奇数肯定不满足
            return new int[0];
        }

        int diff = sum / 2 - sum1;
        for (int arr : array1) {
            int target = diff + arr;
            if (set.contains(target)) {
                // 差值 + arr 在哈希集合中
                return new int[]{arr, target};
            }
        }
        return new int[0];
    }
}